package com.cat.greedyAlgorithm;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/largest-palindromic-number/
 * @create 2025/10/9 15:59
 * @since JDK17
 */

public class Solution67 {
    public String largestPalindromic(String num) {
        int[] h = new int[10];
        int n = num.length(), left = 0, mid = 0;
        char[] ans = new char[n];
        for (var c : num.toCharArray()) {
            h[c - '0']++;   // 统计这个数字出现了多少次
        }
        for (int i = 9; i > 0; i--) {
            if (mid == 0 && h[i] % 2 == 1) {    // 奇数
                mid = i;
            }
            for (int j = h[i] / 2; j > 0; j--) {
                ans[left++] = ((char) (i + '0'));
            }
        }
        if (left == 0) {
            if (mid == 0) {
                return "0";
            } else {
                return String.valueOf(mid);
            }
        }

        for (int i = h[0] / 2; i > 0; i--) {
            ans[left++] = '0';
        }
        int m = left;
        ans[m++] = ((char) (mid + '0'));
        for (int i = left - 1; i >= 0; i--) {
            ans[m++] = ans[i];
        }

        return new String(ans, 0, m);
    }
}
